Sieve p(100000);
void solve()
{
  int n, q;
  cin >> n >> q;

  vi a(n + 1), pos(100005, n + 1);

  vvi f(20, vi(n + 2, n + 1));
  rep(i, 1, n) {
    cin >> a[i];
  }
  per(i, n, 1) {
    auto fac = p.getPrimeFactor(a[i]);
    for (auto &[y, c]: fac) {
      f[0][i] = min(f[0][i], pos[y]);
      pos[y] = i;
    }
    f[0][i] = min(f[0][i], f[0][i + 1]);
  }

  rep(i, 1, 19) {
    rep(j, 1, n) {
      f[i][j] = f[i - 1][f[i - 1][j]];
    }
  }
  
  auto calc = [&](int l, int r) {
    int ans = 0;
    per(i, 19, 0) {
      if (f[i][l] <= r) {
        l = f[i][l];
        ans += 1 << i;
      }
    }
    return ans + 1;
  };

  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << calc(l, r) << '\n';
  }
}